package likou.tanxin;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author: Tangxz
 * @email:1171702529@qq.com
 * @cate: 2020/11/05 14:24
 */
public class _842 {
    public static void main(String[] args) {
        System.out.println(splitIntoFibonacci("123456579"));
    }

    private static Deque<Integer> path=new ArrayDeque<>();
    public static List<Integer> splitIntoFibonacci(String S) {
        dfs(S,0,0,0,0);
        return new ArrayList<>(path);
    }

    /**
     *
     * @param s 原字符串
     * @param idx 当前遍历到的位置
     * @param pre1 前面第二个值
     * @param pre2 前面第一个值
     * @param deep
     * @return
     */
    public static boolean dfs(String s,int idx,int pre1,int pre2,int deep){
        if(idx==s.length()){
            return deep>=3;
        }

        for(int i=idx;i<s.length();i++){
            //获取当前值
            long value=fetchCurrentValue(s,idx,i);
            //如果当前值越界、当前值为0、当前值大于前两个值之和
            if(value>Integer.MAX_VALUE||value<0||(deep!=0&&deep!=1&&value>pre1+pre2)){
                break;
            }
            int res=(int)value;
            if(deep==0||deep==1||(res==pre1+pre2)){
                path.addLast(res);
                if(dfs(s,i+1,pre2,res,deep+1)) {
                    return true;
                }
                path.removeLast();
            }
        }
        return  false;
    }

    /**
     * @param s
     * @param left
     * @param right
     * @return 获取当前字符串截取的值
     */
    public static long fetchCurrentValue(String s,int left,int  right){
        if(right>left&&s.charAt(left)=='0'){
            return -1;
        }
        long res=0;
        for(int i=left;i<=right;i++){
            res=res*10+(s.charAt(i)-'0');
        }
        return res;
    }
}
